package leetcode.jianzhioffer;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-11-06 13:33
 **/
public class JianZhiOffer41 {

    /*List<Integer> list;
    int size;
    *//** initialize your data structure here. *//*
    public MedianFinder() {
        list = new ArrayList<>();
    }

    public void addNum(int num) {
        if (size == 0) {
            list.add(num);
        } else {
            if (num > list.get(size - 1)) {
                list.add(num);
            } else {
                int i = 0;
                while (num > list.get(i)) {
                    i++;
                }
                list.add(i, num);
            }
        }
        size++;
    }

    public double findMedian() {
        if ((size & 1) == 1) {
            return list.get(size / 2);
        }
        return ((double) list.get((size - 1) / 2) + list.get(size / 2)) / 2;
    }*/


    /*//存储较大的一半元素
    Queue<Integer> big;
    //存储较小的一半元素
    Queue<Integer> small;

    *//** initialize your data structure here. *//*
    public MedianFinder() {
        //小顶堆big
        big = new PriorityQueue<>();
        //大顶堆small
        small = new PriorityQueue<>((x, y) -> (y - x));
    }

    public void addNum(int num) {
        if (big.size() == small.size()) {
            small.offer(num);
            big.offer(small.poll());
        } else {
            big.offer(num);
            small.offer(big.poll());
        }
    }

    public double findMedian() {
        return big.size() != small.size() ? big.peek() : (big.peek() + small.peek()) / 2.0;
    }*/
}
